// https://www.lintcode.com/problem/best-time-to-buy-and-sell-stock-iii

public class Solution {
    /**
     * @param prices: Given an integer array
     * @return: Maximum profit
     */
    public int maxProfit(int[] prices) {
        // write your code here
        if (prices.length == 0) {
          return 0;
        }
        int ret = 0;
        int maxProfit = 0;
        int minPrice = prices[0];
        int maxPrice = prices[prices.length - 1];
        int[] profits = new int[prices.length]; // 每个位置交易的最大利润
        Arrays.fill(profits, 0);
        for (int i = 1; i < prices.length; ++i) { // 顺序
          int profit = prices[i] - minPrice;
          if (profit < 0) {
            minPrice = prices[i]; // 更新最低价
          } else {
            if (profit > maxProfit) {
              maxProfit = profit;
            }
          }
          profits[i] = maxProfit;
        }
        maxProfit = 0;
        for (int i = (prices.length - 2); i >= 0; --i) { // 逆序
          int profit = maxPrice - prices[i];
          if (profit < 0) {
            maxPrice = prices[i]; // 更新最高价
          } else {
            if (profit > maxProfit) {
              maxProfit = profit;
            }
            if ((maxProfit + profits[i]) > ret) { // 有先买后卖的限制
              ret = maxProfit + profits[i];
            }
          }
        }
        return ret;
    }
}